CF 1969C

是的你当然会想到动态规划，状态也很好设计（见解答），难点只在于状态转移。如何设计操作次数增加时的状态转移？如何去除动态规划第一维从 $i$ 转移到 $i+1$ 时不清楚 $a_{i-1}$ 是否被修改的影响？

对于一个长为 $n$ 的任意序列，恰好需要 $(n-1)$ 次操作即可将序列的所有元素都更改为该序列的最小值。

$k$ 很小，可以枚举，因此很轻松就会想到使用动态规划：

• 状态设计：设 ${\mathit{dp}}_{i,j}$ 代表序列的前 $i$ 个元素进行 $j$ 次操作后得到的最小值。
• 初始状态：${\mathit{dp}}_{i,0}$ 即为序列的前缀和。
• 最终答案：$\underset{j=0}{\overset{k}{min}}{\mathit{dp}}_{n,j}$
• 状态转移方程：

$${\mathit{dp}}_{i+d,j+d-1}={\mathit{dp}}_{i,j}+d\times \underset{p=i+1}{\overset{i+d}{min}}{a}_p,1\le d\le min\{n-i,k-j+1\}$$

解释：不增加操作次数的转移与提示二给出的性质是显然的，不再解释。利用这些性质，我们可以考虑对当前已经转移到的 ${\mathit{dp}}_{i,j}$ 增加一个长度为 $d$ 的序列，该序列经过 $(d-1)$ 次操作其所有元素均已经修改为序列中的最小值。与此同时注意到 $d=1$ 时 $d-1=0$，因此增加一个长为 $1$ 的序列不需要进行修改，这与我们的认知是吻合的，增强了我们对于该转移正确性的信心。

因此，转移时多枚举一次 $d$ 的值，转移方程中第二项的部分序列的最小值可以顺带求出，因此我们可以在 $\mathcal{O}(n{k}^2)$ 的时间复杂度与 $\mathcal{O}(nk)$ 的空间复杂度下完成要求。